home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / lib / H / access / nobtree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  6.4 KB  |  228 lines
  1. /*
  2.  *  btree.h -- header file for postgres btree access method implementation.
  3.  *
  4.  *    $Header: /private/postgres/src/lib/H/access/RCS/nobtree.h,v 1.6 1991/06/26 19:12:14 mao Exp $
  5.  */
  6.  
  7. #ifdef NOBTREE
  8.  
  9. /* exactly one of these must be defined */
  10. #undef    SHADOW
  11. #undef    NORMAL
  12. #define    REORG
  13.  
  14. /*
  15.  *  NOBTPageOpaqueData -- At the end of every page, we store a pointer to
  16.  *  both siblings in the tree.  See Lehman and Yao's paper for more info.
  17.  *  In addition, we need to know what sort of page this is (leaf or internal),
  18.  *  and whether the page is available for reuse.
  19.  *
  20.  *  Lehman and Yao's algorithm requires a ``high key'' on every page.  The
  21.  *  high key on a page is guaranteed to be greater than or equal to any key
  22.  *  that appears on this page.  Our insertion algorithm guarantees that we
  23.  *  can use the initial least key on our right sibling as the high key.  We
  24.  *  allocate space for the line pointer to the high key in the opaque data
  25.  *  at the end of the page.
  26.  *
  27.  *  Rightmost pages in the tree have no high key.
  28.  */
  29.  
  30. typedef struct NOBTPageOpaqueData {
  31. #ifdef    SHADOW
  32.     uint32        nobtpo_linktok;
  33.     PageNumber    nobtpo_prev;
  34.     PageNumber    nobtpo_oldprev;
  35.     uint32        nobtpo_prevtok;
  36.     PageNumber    nobtpo_next;
  37.     PageNumber    nobtpo_oldnext;
  38.     uint32        nobtpo_nexttok;
  39.     uint32        nobtpo_repltok;
  40.     PageNumber    nobtpo_replaced;
  41.     uint16        nobtpo_flags;
  42. #endif    /* SHADOW */
  43. #ifdef    REORG
  44.     uint32        nobtpo_linktok;    /* to guarantee one split/sync */
  45.     PageNumber    nobtpo_prev;
  46.     PageNumber    nobtpo_oldprev;
  47.     uint32        nobtpo_prevtok;
  48.     PageNumber    nobtpo_next;
  49.     PageNumber    nobtpo_oldnext;
  50.     uint32        nobtpo_nexttok;
  51.     LocationIndex    nobtpo_oldlow;
  52.     uint16        nobtpo_flags;
  53. #endif    /* REORG */
  54. #ifdef    NORMAL
  55.     PageNumber    nobtpo_prev;
  56.     PageNumber    nobtpo_next;
  57.     uint16        nobtpo_flags;
  58.     uint16        nobtpo_filler;
  59. #endif    /* NORMAL */
  60.  
  61. #define NOBTP_LEAF    (1 << 0)
  62. #define NOBTP_ROOT    (1 << 1)
  63. #define NOBTP_SIBOK    (1 << 3)
  64. #define NOBTP_FREE    (1 << 4)
  65.  
  66. } NOBTPageOpaqueData;
  67.  
  68. typedef NOBTPageOpaqueData    *NOBTPageOpaque;
  69.  
  70. /*
  71.  *  ScanOpaqueData is used to remember which buffers we're currently
  72.  *  examining in the scan.  We keep these buffers locked and pinned and
  73.  *  recorded in the opaque entry of the scan in order to avoid doing a
  74.  *  ReadBuffer() for every tuple in the index.  This avoids semop() calls,
  75.  *  which are expensive.
  76.  */
  77.  
  78. typedef struct NOBTScanOpaqueData {
  79.     Buffer    nobtso_curbuf;
  80.     Buffer    nobtso_mrkbuf;
  81. } NOBTScanOpaqueData;
  82.  
  83. typedef NOBTScanOpaqueData    *NOBTScanOpaque;
  84.  
  85. typedef struct NOBTIItemData {
  86. #ifdef    SHADOW
  87.     PageNumber        nobtii_oldchild;
  88.     PageNumber        nobtii_child;
  89.     unsigned short        nobtii_info;
  90.     unsigned short        nobtii_filler;       /* must longalign key */
  91. #endif    /* SHADOW */
  92. #ifdef    REORG
  93.     PageNumber        nobtii_child;
  94.     unsigned short        nobtii_info;
  95. #endif    /* REORG */
  96. #ifdef    NORMAL
  97.     PageNumber        nobtii_child;
  98.     unsigned short        nobtii_info;
  99. #endif    /* NORMAL */
  100.     /* MORE DATA FOLLOWS AT END OF STRUCT */
  101. } NOBTIItemData;
  102.  
  103. typedef NOBTIItemData    *NOBTIItem;
  104.  
  105. #define NOBTIItemGetSize(i)    ((i)->nobtii_info & 0x1FFF)
  106. #define NOBTIItemGetDSize(i)    ((i).nobtii_info & 0x1FFF)
  107.  
  108. typedef struct NOBTLItemData {
  109.     IndexTupleData        nobtli_itup;
  110.     /* MORE DATA FOLLOWS AT END OF STRUCT */
  111. } NOBTLItemData;
  112.  
  113. typedef NOBTLItemData    *NOBTLItem;
  114.  
  115. /*
  116.  *  NOBTStackData -- As we descend a tree, we push the (key, pointer) pairs
  117.  *  from internal nodes onto a private stack.  If we split a leaf, we use
  118.  *  this stack to walk back up the tree and insert data into parent nodes
  119.  *  (and possibly to split them, too).  Lehman and Yao's update algorithm
  120.  *  guarantees that under no circumstances can our private stack give us
  121.  *  an irredeemably bad picture up the tree.  Again, see the paper for
  122.  *  details.
  123.  *
  124.  *  For the no-overwrite algorithm, we store the keys that bound the link
  125.  *  we traverse in the tree in the stack.  When we reach the child, we use
  126.  *  these keys to verify that we traversed an active link.
  127.  */
  128.  
  129. typedef struct NOBTStackData {
  130.     PageNumber        nobts_blkno;
  131.     OffsetIndex        nobts_offset;
  132.     NOBTIItem        nobts_btitem;
  133. #ifdef    REORG
  134.     NOBTIItem        nobts_nxtitem;
  135. #endif    /* REORG */
  136. #ifdef    SHADOW
  137.     NOBTIItem        nobts_nxtitem;
  138. #endif    /* SHADOW */
  139.     struct NOBTStackData    *nobts_parent;
  140. } NOBTStackData;
  141.  
  142. typedef NOBTStackData    *NOBTStack;
  143.  
  144. /*
  145.  *  We need to be able to tell the difference between read and write
  146.  *  requests for pages, in order to do locking correctly.
  147.  */
  148.  
  149. #define    NOBT_READ    0
  150. #define    NOBT_WRITE    1
  151.  
  152. /*
  153.  *  Similarly, the difference between insertion and non-insertion binary
  154.  *  searches on a given page makes a difference when we're descending the
  155.  *  tree.
  156.  */
  157.  
  158. #define NOBT_INSERTION    0
  159. #define NOBT_DESCENT    1
  160.  
  161. /*
  162.  *  In general, the btree code tries to localize its knowledge about page
  163.  *  layout to a couple of routines.  However, we need a special value to
  164.  *  indicate "no page number" in those places where we expect page numbers.
  165.  */
  166.  
  167. #define P_NONE        0
  168.  
  169. /*
  170.  *  Strategy numbers -- ordering of these is <, <=, =, >=, > 
  171.  */
  172.  
  173. #define NOBTLessStrategyNumber        1
  174. #define NOBTLessEqualStrategyNumber    2
  175. #define NOBTEqualStrategyNumber        3
  176. #define NOBTGreaterEqualStrategyNumber    4
  177. #define NOBTGreaterStrategyNumber    5
  178. #define NOBTMaxStrategyNumber        5
  179.  
  180. /*
  181.  *  When a new operator class is declared, we require that the user supply
  182.  *  us with an amproc procudure for determining whether, for two keys a and
  183.  *  b, a < b, a = b, or a > b.  This routine must return < 0, 0, > 0,
  184.  *  respectively, in these three cases.  Since we only have one such proc
  185.  *  in amproc, it's number 1.
  186.  */
  187.  
  188. #define NOBTORDER_PROC    1
  189.  
  190. /* public routines */
  191. char            *nobtgettuple();
  192. InsertIndexResult    nobtinsert();
  193.  
  194. /* private routines */
  195. InsertIndexResult    _nobt_doinsert();
  196. InsertIndexResult    _nobt_insertonpg();
  197. OffsetIndex        _nobt_pgaddtup();
  198. ScanKey            _nobt_mkscankey();
  199. ScanKey            _nobt_imkscankey();
  200. NOBTStack        _nobt_search();
  201. NOBTStack        _nobt_searchr();
  202. void            _nobt_relbuf();
  203. Buffer            _nobt_getbuf();
  204. void            _nobt_wrtbuf();
  205. void            _nobt_wrtnorelbuf();
  206. bool            _nobt_skeycmp();
  207. OffsetIndex        _nobt_binsrch();
  208. OffsetIndex        _nobt_firsteq();
  209. Buffer            _nobt_getstackbuf();
  210. RetrieveIndexResult    _nobt_first();
  211. RetrieveIndexResult    _nobt_next();
  212. RetrieveIndexResult    _nobt_endpoint();
  213. bool            _nobt_step();
  214. bool            _nobt_twostep();
  215. StrategyNumber        _nobt_getstrat();
  216. bool            _nobt_invokestrat();
  217. NOBTLItem        _nobt_formitem();
  218. NOBTIItem        _nobt_formiitem();
  219. bool            _nobt_goesonpg();
  220. void            _nobt_regscan();
  221. void            _nobt_dropscan();
  222. void            _nobt_adjscans();
  223. void            _nobt_scandel();
  224. bool            _nobt_scantouched();
  225. OffsetIndex        _nobt_findsplitloc();
  226.  
  227. #endif /* NOBTREE */
  228.